package JDK常用类库.蓝桥杯准备;

import java.math.BigInteger;
import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Calendar;

/**蓝桥备赛
 * 输入类文件信息，一定要注意：类文件名称必须是 Main且包名必须为空！不符合要求会导致比赛时提交代码无效！
 *
 * 1.数学运算时,注意精度问题
 * 2.日期类的使用
 * 3.最大公约数,最小公倍数,质数(1.判断是否是质数;2.判断范围内质数的个数)
 * 4.位运算
 * 5.判断回文数
 * 6.二分查找
 * 7.eclipse常用快捷键及其使用
 * ctrl 快捷键
 * ctrl + z：撤回 ctrl + 1：修复代码,常用在"编译前查错"(快速导包)
 * Alt快捷键
 * alt + /：单词补全
 * alt + ↑\↓：该行向上\下移动
 * @author zx
 * @create 2022-04-06 16:11
 */
public class Test1 {
    /**
     * gcd函数(欧几里得算法原理)
     * @return 返回值则是a和b的最大公约数
     */
    public static int gcd(int a,int b) {
        return b == 0 ? a : gcd(b,a % b);
    }

    /**
     * lcm函数(速求最小公倍数,原理基于gcd函数)
     * @return 返回值为a和b的最小公倍数
     */
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a,b);//最小公倍数 = 两数之积 ÷ 两数最大公约数
    }

    /**
     * 使用JDK内置函数求最大公约数、最小公倍数
     */
    public static void main10(String[] args) {
        BigInteger a = new BigInteger("12");
        BigInteger b = new BigInteger("6");
        BigInteger gcd = a.gcd(b);
        //数学性质：a * b = lcm(a,b) * gcd(a,b)
        BigInteger lcm = a.multiply(b).divide(gcd);
        System.out.println(gcd);//最大公约数
        System.out.println(lcm);//最小公倍数
    }
    /**
     * @ 埃筛法
     * 埃筛法是能够快速筛选出质数的方法之一,在众多质数筛选方法中,埃筛法虽然不是最快的方法,
     * 但绝对是最容易理解的方法。
     * 原理：从小到大开始筛选质数,当某个数被认定为质数时,那么后面能够被该数整除的数就一定不是质数,为这些数增加一个标记,
     * 当遍历到这些被标记的数时,直接跳过即可,无需再为其执行检验是否为质数的操作,因为判断一个数是否为质数是筛选质数过程中
     * 最耗时的操作,而埃筛法则能大幅度的减少该操作的执行频率,从而提高素数筛选的效率。
     */
    //求n下有多少个质数
    public static void prime(int n) {
        boolean[] flag = new boolean[n + 1];
        for(int i = 2; i <= n; i++) {
            if(flag[i]){
                continue;
            }
            System.out.print(i + "  ");
            for(int j = i; i * j <= n; j++) {
                flag[i * j] = true;
            }
        }
    }
    private static boolean isPrime(int n){
        int i;
        for(i = 2;i <= Math.sqrt(n);i++){
            //只要模一次是0,就不是素数
            if(n % i == 0){
                return false;
            }
        }
        return i > Math.sqrt(n);//是素数
    }

    /**
     * 进制转换
     */
    public static void conversion(){
        //n进制转为十进制
        System.out.println(Integer.valueOf("1111",2));
        System.out.println(Integer.valueOf("ffff",16));
        //十进制转为n进制
        System.out.println(Integer.toString(128,2));
        System.out.println(Integer.toString(15,16));
    }

    /**
     * @param args 保留小数
     */
    public static void main2(String[] args) {
        // 保留两位小数
        System.out.printf("%.2f",10.23144);
    }

    /**
     * 在第 1个棋盘格放 1 粒麦子，在第 2 个棋盘格放 2 粒麦子，在第 3 个棋盘格放 4 粒麦子，
     * 在第 4 个棋盘格放 8 粒麦子，...后一格的数字是前一格的两倍，直到放完所有棋盘格（国际象棋共有 64 格）。
     */
    public static void main(String[] args) {
        BigInteger a = new BigInteger("1");
        BigInteger b = new BigInteger("2");
        BigInteger res = new BigInteger("1");
        for (int i = 2; i <= 64; i++) {
            a = a.multiply(b);
            res = res.add(a);
        }
        System.out.println(res);//18446744073709551615
        System.out.println(Integer.MAX_VALUE);//2147483647
    }

    /**
     * 给定数列 1, 1, 1, 3, 5, 9, 17,……从第 4 项开始，每项都是前 3 项的和。
     * 求第 20190324 项的最后 4 位数字。
     */
    public static void main6(String[] args) {
        int a = 1;
        int b = 1;
        int c = 1;
        int d = 0;
        for (int i = 4; i <= 20190324; i++) {
            d = a + b + c;
            d = d % 10000;
            a = b;
            b = c;
            c = d;
        }
        System.out.println(d);//4659
    }

    /**
     * @return 判断回文数
     */
    public boolean isPalindrome(int x) {
        String str = String.valueOf(x);
        char[] c = str.toCharArray();
        int mid = c.length / 2;
        int left = 0;
        int right = c.length - 1;
        while(left <= right){
            if(c[left] != c[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    /**
     * @return 求二进制中1的个数
     */
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            n = n & (n - 1);
            res++;
        }
        return res;
    }
    /**
     * @return 快速幂
     * 虽然可以使用Java数学包下的Math.pow方法来求出x的n次幂的值,但这个函数本身运行起来是非常耗时的
     * 对于需要参加竞赛的读者来说,无疑会在超时的边缘徘徊,而快速幂可以通过将指数拆分成多个因数相乘的形式来简化幂运算
     * 大大调高运算效率,可谓是我们的一大得力帮手！
     * 比如要求x^11,正常的乘积需要循环乘11次,时间复杂度为O(n)
     * 快速幂的思想就是将指数11可以转成二进制数1011,则原来的式子可以转化成
     * x^11 = x^(2^3 + 2^1 + 2^0).此时只运算了3次乘积,时间复杂度降至O(logn)
     * 只有在1的位置上,才有相应的权重,这也就是为什么需要通过与运算：(b & 1) == 1判断最后一位是否为1
     */
    public double myPow(double x, int n) {
        double res = 1;
        long v = n;//为了保证-n不溢出,先转换成long类型
        if(v < 0) {//如果v小于0,求1/x的-v次方
            x = 1 / x;
            v = -v;
        }
        // 在对v进行二进制拆分的同时计算答案
        while(v > 0) {
            // 如果v二进制表示的最低位为 1,需要计入贡献
            if((v & 1) == 1) {//此处等价于if(v % 2 == 1)
                res *= x;
            }
            // 舍弃 v 二进制表示的最低位,每次只要判断最低位即可
            v >>= 1;//此处等价于v = v / 2
            x *= x;//将贡献不断地平方
        }
        return res;
    }

    /**
     * 1999年12月31日是星期五，请问：未来哪一个离我们最近的一个世纪末年(即XX99年)的12月31日
     * 正好是星期天？回答年份
     */
    public void judgeYear() {
        // 注意Calendar实例的获取方式
        Calendar calendar = Calendar.getInstance();
        for (int year = 1999; year < 10000; year += 100) {
            // 设置年月日
            calendar.set(Calendar.YEAR, year);
            calendar.set(Calendar.MONTH, 11);// 其实是12月
            calendar.set(Calendar.DAY_OF_MONTH, 31);
            if (calendar.get(Calendar.DAY_OF_WEEK) == 1) {
                // sunday是第一天，所以为1时是Sunday,通过源码查看
                System.out.println(year);// 2299
                break;
            }
        }
    }

    /**
     * 跑步锻炼
     * 方法二：模拟
     */
    static int[] M = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    public void paobu() {
        int y = 2000, m = 1, d = 1, w = 6, ans = 0;
        while (y != 2020 || m != 10 || d != 1) {
            if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) {//判断闰年
                M[2] = 29;
            } else {
                M[2] = 28;// M是全局变量
            }
            d++;
            w = (w + 1) % 7;// w为0为星期天
            if (d > M[m]) {
                d = 1;
                m++;
            }
            if (m > 12) {
                m = 1;
                y++;
            }
            if (d == 1 || w == 1) {
                ans++;// 是月初或者周一多加一次
            }
            ans++;
        }
        // 这个循环是先加值再加日期,所以2020.10.1号的已经加上去了,但是2000.1.1没加上,所以加2
        ans += 2;
        System.out.println(ans);// 8879
    }
    /**
     * @param args 两个日期相差的天数
     *
     * 求2022-2-1到2022-3-1相差的天数
     *
     * 求两个日期的时间差(可以以天、小时、分钟、秒为单位输出)
     */
    public static void main3(String[] args) {
        LocalDateTime time1 = LocalDateTime.of(2022, 2, 1, 0, 0);
        LocalDateTime time2 = LocalDateTime.of(2022, 3, 1, 0, 0);
        long result = Duration.between(time1, time2).toDays(); // 28

        LocalDateTime time3 = LocalDateTime.of(2022,5,13,13,13,59,23);
        LocalDateTime time4 = LocalDateTime.of(2022,5,14,13,13,59,23);
        int res = (int) Duration.between(time3,time4).toMinutes();
    }

    /**
     * @param args 遍历某段日期的每一天
     *
     * 遍历2022-01-01到2022-03-01这段日期中的每一天
     *
     * 例题：跑步锻炼
     * 正常情况下,小蓝每天跑 1 千米.如果某天是周一或者月初(1 日),为了激励自己,小蓝要跑 2 千米.
     * 如果同时是周一或月初,小蓝也是跑 2 千米.
     * 小蓝跑步已经坚持了很长时间,从 2000 年 1 月 1 日周六(含)到 2020 年 10 月 1 日周四(含).
     * 请问这段时间小蓝总共跑步多少千米？
     */
    public static void main4(String[] args) {
        Calendar c = Calendar.getInstance();
        c.set(Calendar.YEAR, 2000);
        c.set(Calendar.MONTH, 0);
        c.set(Calendar.DAY_OF_MONTH, 1);
        int res = 0;
        for(;;){
            if(c.get(Calendar.DAY_OF_WEEK) == 2 || c.get(Calendar.DATE) == 1){
                res += 2;
            }else{
                res += 1;
            }
            if(c.get(Calendar.YEAR) == 2020 && c.get(Calendar.MONTH) == 9 &&
                    c.get(Calendar.DAY_OF_MONTH) == 1){
                break;
            }
            c.add(Calendar.DATE, 1);//天数自增1
        }
        System.out.println(res);
    }
}
